<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>选择排序</title>
</head>
<body>
    <script>
        //先从数组的开头,中间和结尾使用三数取中法取得中间值,然后将基准和开始的元素进行交换,此时开头的元素就是基准
        //找到基准后,先从右边开始,直到找到一个小于基准的数,然后进行交换,然后再从开始的下一个元素开始找,直到找到一个大于基准的数,再进行交换,直至将基准放到中间(左边的都比基准小,右边的都比基准大),
        //然后再对两边的序列进行同样的排序,直至剩下唯一一个元素为止
        let array = [3,12,4,5,2,7,6];
        let left = 0;
        let right = array.length - 1;
        function quick(array,left,right){
            if(left >= right) return;
            let x = findF(array,left,right);
            
            //交换基准到开头
            let tmp = array[x];
            array[x] = array[left];
            array[left] = tmp;

            let pivot = partition(array,left,right);
            quick(array,left,pivot - 1);
            quick(array,pivot + 1,right);
        }
        
        //三数取中法
        function findF(array,left,right){
            let mid = Math.floor((left + right) / 2);
            if(array[right] > array[left]){
                if(array[left] > array[mid]){
                    return left;
                }else if(array[right] < array[mid]){
                    return right;
                }else{
                    return mid;
                }
            }else{
                if(array[mid] > array[left]){
                    return left;
                }else if(array[mid] < array[right]){
                    return right;
                }else{
                    return mid;
                }
            }
        }
        
        //挖坑法
        function partition(array,left,right){
            let num = array[left];
            while(left < right){
                while(left < right && array[right] >= num){
                    right --;
                }//右边找到小于这个数的值，并交换
                array[left] = array[right];
                while(left < right && array[left] <= num){
                    left ++;
                }//左边找到大于这个数的值，并交换
                array[right] = array[left];

            }
            array[left] = num;//最后埋坑
            return left;
        }
        quick(array,0,array.length - 1);
        console.log(array);
    </script>
</body>
</html>